/*
Date:20210413 21:24pm
key:1.(一定要在第一个，倒数第一个不能是它
    2.总长2*n
    3.每次准备放入字符串的时候都检查一次是不是合格。
*/
class Solution {
public:
    //写个函数判断字符串符不符合条件
    bool match(string&t)
    {
        stack<char>S;
        
        for(int i=0;i<t.size();i++)
        {
            if(i==0)
            {S.push(t[0]);
               
            }
            else
            {
                if(t[i]==')'&&S.top()=='(')
                { S.pop();}
                else
                {

                    S.push(t[i]);
                }
            }
        }
        
        return S.size()==0?1:0;
    }
    //回溯
    void back_t(vector<string>&V,int&count,string&t,int&n)
    {
        if(t.size()==2*n)
        {
            if(match(t)){V.push_back(t);}
        }
        else
        {
                //第一个必须要放，最后一个不能放
                if(count<n&&t.size()!=2*n-1)
                {
                t+='(';
                count++;
                back_t(V,count,t,n);
                count--;
                t.erase(t.end()-1);
                }
                //有(才能放
                if(count>0)
                {
                t+=')';
                count--;
                back_t(V,count,t,n);
                count++;
                t.erase(t.end()-1);
                }
    
        
        }
    }
    vector<string> generateParenthesis(int n)
    {
        //有一个(就加1，一个)-1.等于0下，只能加1，如果大于0,可加1或可减1，字符串大小为2*n的时候停止。
        int count=0;
        vector<string>V;
        string t="";
        t+='(';
        count++;
        back_t(V,count,t,n);
        return V;
    }
};